package array;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums 和一个整数 k 。你需要找到 nums 中长度为 k 的 子序列 ，且这个子序列的 和最大 。
 * 请你返回 任意 一个长度为 k 的整数子序列。
 * 子序列 定义为从一个数组里删除一些元素后，不改变剩下元素的顺序得到的数组。
 * <p>
 * 示例 1：
 * 输入：nums = [2,1,3,3], k = 2
 * 输出：[3,3]
 * 解释：
 * 子序列有最大和：3 + 3 = 6 。
 * <p>
 * 示例 2：
 * 输入：nums = [-1,-2,3,4], k = 3
 * 输出：[-1,3,4]
 * 解释：
 * 子序列有最大和：-1 + 3 + 4 = 6 。
 * <p>
 * 示例 3：
 * 输入：nums = [3,4,3,3], k = 2
 * 输出：[3,4]
 * 解释：
 * 子序列有最大和：3 + 4 = 7 。
 * 另一个可行的子序列为 [4, 3] 。
 *
 * @author Jisheng Huang
 * @version 20250628
 */
public class MaxSubsequence_2099 {
    /**
     * 先对下标排序，取出k个最大的下标数组，再对下标数组排序，保证是数组原顺序的子序列
     *
     * @param nums the given array
     * @param k    the length of the result array
     * @return the largest subarray with length k
     */
    public static int[] maxSubsequence(int[] nums, int k) {
        // Create the index array
        Integer[] idx = new Integer[nums.length];
        // Set the index array
        Arrays.setAll(idx, i -> i);
        // Sort inverse order of the index array according to the given array
        Arrays.sort(idx, (i, j) -> nums[j] - nums[i]);

//        for (int i : idx) {
//            System.out.print(i + " ");
//        }
//        System.out.println();

        // 对前K个下标排序
        int[] ans = new int[k];

        for (int i = 0; i < k; ++i) {
            ans[i] = idx[i];
        }

//        for (int i : ans) {
//            System.out.print(i + " ");
//        }
//        System.out.println();

        Arrays.sort(ans);

        // 取出nums子序列
        for (int i = 0; i < k; ++i) {
            ans[i] = nums[ans[i]];
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 3, 3};
        int k = 2;

        int[] ans = maxSubsequence(nums, k);

        for (int i : ans) {
            System.out.print(i + " ");
        }
        System.out.println();

        nums = new int[]{3, 4, 3, 3};
        k = 3;

        ans = maxSubsequence(nums, k);

        for (int i : ans) {
            System.out.print(i + " ");
        }
    }
}
